Máquina de Turing universal

Máquina de Turing
Máquina
Máquina de Turing universal Máquina de Turing alternada Máquina de Turing quântica Máquina de Turing não determinística Máquina de Turing somente de leitura Máquina de Turing movimentação à direita Máquina de Turing probabilística Máquina de Turing multifita Máquina de Turing de Várias Faixas Máquinas de Turing equivalentes Exemplos de Máquinas de Turing
Ciência
Alan Turing Categoria:Máquina de Turing

Em ciência da computação, uma máquina de Turing universal (MTU) é uma máquina de Turing que consegue simular outra máquina de Turing arbitrária com uma entrada arbitrária. Essencialmente, essa máquina universal realiza a simulação lendo tanto a descrição da máquina a ser simulada quanto sua respectiva entrada representada pelo conteúdo de sua fita. Alan Turing apresentou essa máquina em 1936–1937. Este modelo é considerado por alguns (por exemplo, Martin Davis (2000)), como a origem do computador com programa armazenado —usado por John von Neumann (1946), que atualmente leva seu nome: a Arquitetura de von Neumann. Esta máquina também é conhecida como máquina de computação universal, máquina universal, máquina U ou simplesmente U. Em termos de complexidade computacional, uma máquina de Turing universal multi-fita é mais lenta apenas por um fator logarítmico comparada às máquinas que ela simula.

Introdução

Toda máquina de Turing computa uma certa função computável parcial fixa a partir de uma cadeia como entrada formada pelos símbolos de seu alfabeto. Dessa maneira, ela se comporta como um computador com um programa fixo. Entretanto, podemos codificar a tabela de ação de qualquer máquina de Turing numa cadeia. Assim, podemos construir uma máquina de Turing que possui, em sua fita, uma cadeia que descreve a tabela de ação, seguida por uma cadeia descrevendo sua fita de entrada, e finalmente computar a fita que a máquina de Turing codificada computaria. Turing descreveu essa construção detalhadamente no seu artigo em 1936:

"É possível criar uma máquina que pode ser usada para computar qualquer sequência computável. Se fornecida para uma máquina U uma fita, na qual em seu início seja escrito a D.P. ["descrição padrão" de uma tabela de ação] de alguma máquina de computação M, então U computará a mesma sequência de M, assim como ela a faria."

Computador com programa armazenado

Davis apresentou um argumento convincente de que a concepção de Turing sobre o que é conhecido como "computador com programa armazenado" (que coloca a "tabela de ação"—instruções para a máquina-na mesma "memória" como dado de entrada) influenciou fortemente John von Neumann na concepção do primeiro computador baseado em símbolos discretos (ao contrário de análogos), o EDVAC. Para isso, Davis cita na revista Time que todos que digitam num teclado estão trabalhando numa encarnação de uma máquina de Turing e que John von Neumann trabalhou apoiado na obra de Alan Turing. Davis introduz a hipótese que a Máquina Automática de Computação (en: ACE) "antecipou" as noções de microprogramação (microcódigo) e processadores RISC (Davis 2000:188). Knuth cita a obra de Turing no computador ACE com um projeto de hardware para facilitar a ligação de subrotinas (Knuth 1973:225); Davis também faz referência à obra como o uso "Turing" de uma pilha em hardware (Davis 2000:237 nota de rodapé 18). Como a máquina de Turing estava incentivando a construção de computadores, a MTU estava incentivando o desenvolvimento da incipiente ciência da computação. Um antigo, se não primeiro, montador foi proposto para o EDVAC (Davis 2000:192). O primeiro programa bem composto tinha como objeto simplesmente ordenar dados eficientemente. (Davis 2000:184). Knuth observa que a incorporação do retorno de uma subrotina no próprio programa (em vez de registradores especiais) é atribuível a von Neumann e Goldstine. Knuth ainda afirma que a primeira rotina interpretativa pode ser dita como a "máquina de Turing universal". Rotinas interpretativas, no senso formal foi mencionado por John Mauchly nas suas palestras na Moore School em 1946. Turing também tomou parte do desenvolvimento: sistemas interpretativos para o piloto do computador ACE foi escrito sob sua ideia. (Knuth 1973:226). Davis menciona brevemente sistemas operacionais e compiladores como resultados da noção de programa como um conjunto de dados (Davis 2000:185). Alguns, entretanto, podem levantar questões sobre essa avaliação. Nos meados das décadas de 40 e 50, um grupo relativamente pequeno de pesquisadores estava intimamente envolvido com a arquitetura dos novos "computadores digitais". Hao Wang (1954), um jovem pesquisador nessa época, fez a seguinte observação: a teoria de funções computáveis de Turing antecederam mas não influenciaram em grande escala a extensiva construção atual de computadores digitais. Os dois aspectos de teoria e prática foram desenvolvidos, quase que inteiramente, independentemente um do outro. A razão principal indiscutível é que os lógicos estão interessados em questões radicalmente diferentes daquelas que matemáticos aplicados e engenheiros elétricos estão preocupados. Apesar disso, deve-se destacar que frequentemente conceitos similares são expressados por diferentes termos nos dois ramos de desenvolvimento. (Wang 1954, 1957:63) Wang esperava que seu artigo pudesse "conectar duas abordagens". De fato, Minsky confirma que a primeira formulação da teoria da máquina de Turing em modelos de computação é feita por Wang (1957) (Minsky 1967:200). À respeito da redução de computadores para modelos Turing equivalentes (vice-versa), a indicação de Minsky sobre Wang ter feito "a primeira formulação" está aberta para discussão. Enquanto ambos artigos de Minsky e Wang (1961 / 1957) serem citados por Shepherdson and Sturgis (1963), eles também citam e resumem em alguns detalhes o trabalho dos matemáticos europeus Kaphenst (1959), Ershov (1959) e Péter (1958). Os nomes dos matemáticos Hermes (1954, 1955, 1961) e Kaphenst (1959) aparecem na bibliografia de ambos Sheperdson-Sturgis (1963) e Elgot-Robinson (1961). Outros dois nomes de importância são os pesquisadores canadenses Melzak (1961) e Lambek (1961). Referências podem ser encontradas em Máquina de registro.

Princípio matemático

Com a codificação das tabelas de ação como cadeias, se torna possível para máquinas de Turing, em princípio, responder questões sobre o comportamento de outras máquinas de Turing. Entretanto, a maioria dessas questões são indecidíveis, isto é, a função em questão não pode ser calculada mecanicamente. Por exemplo, o problema de determinar se uma máquina de Turing arbitrária irá parar com uma determinada entrada, ou em qualquer entrada, é conhecido como o Problema da Parada, que demonstrou ser indecidível no artigo original de Turing. Uma máquina universal de Turing pode calcular qualquer função recursiva, decidir qualquer linguagem recursiva e aceitar qualquer linguagem recursivamente enumerável. De acordo com a Tese de Church-Turing, os problemas solúveis por uma máquina de Turing universal são exatamente aqueles problemas solúveis por um algoritmo ou um método efetivo de computação, para qualquer definição razoável desses termos. Por essas razões, a máquina universal de Turing serve como padrão para comparação de sistemas computacionais, e um sistema que simula a máquina de Turing universal é chamada de Turing completa. Uma versão abstrada da máquina de Turing universal é a função universal, uma função computável que pode ser usada para calcular qualquer outra função computável. O teorema MTU prova a existência dessa função.

Eficiência

Sem perder poder de generalização, uma suposta entrada de uma máquina de Turing pode ter o alfabeto {0,1}; qualquer outro alfabeto finito pode ser codificado sobre {0,1}. O comportamento de uma máquina de Turing M é determinado pela sua função de transição. Essa função também pode ser facilmente codificada como uma cadeia sobre um alfabeto {0,1}. O tamanho do alfabeto de M, o número de fitas que ela possui e o tamanho do espaço de estados podem ser deduzidos pela tabela das funções de transição. Os distintos estados e símbolos podem ser identificados por suas posições, por exemplo os dois primeiros estados podem ser, por convenção, os estados de início e de parada, respectivamente. Consequentemente, toda máquina de Turing pode ser codificada como uma cadeia formada sobre o alfabeto {0,1}. Adicionalmente, por convenção, qualquer codificação inválida para uma máquina de Turing trivial para imediatamente, e toda máquina de Turing pode ter uma infinita quantidade de codificações preenchendo-a com uma arbitrária quantidade de 1's no final, assim como funciona os comentários numa linguagem de programação. Não é surpresa que possamos, através dessa codificação, demonstrar a existência de uma numeração de Gödel e a equivalência computacional entre máquinas de Turing e funções µ-recursivas. Similarmente, essa construção associa, para cada cadeia binária a, uma máquina de Turing M_a.

Se baseando pela codificação dada acima, em 1966, F. C. Hennie e R. E. Stearns mostraram que dada uma máquina de Turing M_a que para numa entrada x em N passos, então existe uma máquina de Turing universal multi-fita que para nas entradas a, x (em diferentes fitas) em CN log N, onde C é uma constante específica da máquina que não depende do tamanho da entrada x, mas sim do tamanho do alfabeto de M, números de fitas e números de estados. Na prática, isso é uma simulação O(N log N).

Máquinas menores

Quando Alan Turing surgiu com a ideia de uma máquina universal, ele tinha em mente um modelo de computação simples poderoso o bastante para calcular todas as possíveis funções que podem ser calculadas. Claude Shannon foi o primeiro a explicitar a questão de encontrar a menor máquina de Turing possível, em 1956. Ele mostrou que dois símbolos são suficientes desde que estados suficientes sejam usados (vice-versa), e que sempre é possível trocar estados por símbolos. Marvin Minsky descobriu, em 1962, uma máquina de Turing universal com 7 estados e 4 símbolos usando sistemas 2-tag. Desde então, outras pequenas máquinas de Turing universais vem sendo descobertas por Yurii Rogozhin e outros através da expansão dessa abordagem. Se indicarmos por (m, n) a classe das MTUs com m estados e n símbolos, as seguintes tuplas são encontradas: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), e (2, 18). A máquina Rogozhin (4,6) usa apenas 22 instruções, e nenhuma MTU padrão de menor complexidade de descrição é conhecida. Entretanto, generalizações do modelo padrão da máquina de Turing admitem MTUs ainda menores. Um modo de generalizar é permitir uma infinidade de palavras repetidas num único ou em ambos os lados da entrada de uma máquina de Turing, assim estendendo a definição da universalidade, conhecidas como "semi-fraca" ou "fraca" universalidades, respectivamente. Pequenas máquinas de Turing universais "fracas" que simulam o autômato celular de regra 110 foram dads para os pares símbolo-estado (6,2), (3,3) e (2,4). A prova da universalidade para a máquina de Turing[Wolfram's 2-state 3-symbol Turing machine | Wolfram 2-estados 3-símbolos] amplia ainda mais a noção da universalidade fraca permitindo certas configurações iniciais não-periódicas. Outras variantes do modelo da máquina de Turing padrão que produzem MTUs pequenas incluem máquinas multi-fitas ou fitas com múltiplas dimensões, além de máquinas acopladas com um autômato finito.

Exemplo de codificação de uma MTU

Para aqueles que desejam aceitar o desafio de projetar uma MTU exatamente como Turing especificou, vejam o artigo escrito por Davis em Copeland (2004:103dd). Davis corrige os erros do original e demonstra como seria uma execução de um exemplo. Ele reividica que "rodou" com sucesso uma simulação simplificada.

O seguinte exemplo foi tomado de Turing (1936). Para mais informações sobre esse exemplo, veja a página Exemplos de Máquinas de Turing. Turing usou sete símbolos { A, C, D, R, L, N, ; } para codificar cada 5-tupla; como descrito no artigo Máquina de Turing, suas 5-tuplas são do tipo N1, N2 e N3 exclusivamente. O número de cada "configuração-m" (instrução, estado) é representado por "D", seguido por uma cadeia unária de A's, i.e. "q3" = DAAA. De um modo semelhante, ele codifica os símbolos brancos como "D", o símbolo "0" é "DC", o símbolo "1" como DCC etc. Os símbolos "R", "L" e "N" permanecem como estão. Após codificar, cada 5-tupla é "montada" numa cadeia na ordem estabelecida na tabela seguinte:

Configuração-m atual	Símbolo da fita	Operação-impressão	Movimento da fita	Configuração-m final		Configuração-m atual (código)	Símbolo da fita (código)	Operação-impressão (código)	Movimento da fita (código)	Configuração-m final (código)	5-tupla montada (código)
q1	branco	P0	R	q2		DA	D	DC	R	DAA	DADDCRDAA
q2	branco	E	R	q3		DAA	D	D	R	DAAA	DAADDRDAAA
q3	branco	P1	R	q4		DAAA	D	DCC	R	DAAAA	DAAADDCCRDAAAA
q4	branco	E	R	q1		DAAAA	D	D	R	DA	DAAAADDRDA

Finalmente, juntamos os códigos de todas as quatro 5-tuplas numa cadeia iniciada por ";" e separadas por ";".

Ele colocou essa cadeia em quadrados alternados—os "quadrados-F"—deixando os "quadrados-E" (aqueles passíveis de rasura) vazios. A montagem final da cadeia na fita para a máquina-U consiste em colocar dois símbolos especiais ("e"), um após o outro, separar o código em quadrados alternados e, por último, dois-pontos duplos "::" (vazios serão mostrados aqui pelo símbolo "." para melhor visualização).

A tabela de ação da máquina-U (tabela estado-transição) é responsável pela decodificação dos símbolos. A tabela de ação de Turing mantém o controle com os marcadores "u", "v", "x", "y", "z", colocando-os nos "quadrados-E" à direita do "símbolo marcado"—por exemplo, para marcar a instrução atual, z é colocado à direita de ";", x guarda o local com respeito à "configuração-m" DAA atual. A tabela de ação das máquinas-U deslocarão os símbolos (apagando e recolocando-os em locais diferentes) à medida que a computação prossegue.

Uma porção de outros autores (notavelmente Roger Penrose, no seu livro The Emperor's New Mind) fornecem exemplos de outras maneiras para codificar instruções numa máquina-U. Assim como Penrose, a maioria usa somente símbolos binários, i.e. somente os símbolos {0, 1} ou (branco, marcado |}. Penrose vai mais fundo e escreve seu próprio código para máquina-U por inteiro (Penrose 1989:71-73). Ele afirma que é um verdadeiro código de máquina-U, tão enorme que "alimenta" quase 2 páginas com apenas 1's e 0's. Para leitores interessados em códigos simples para a Máquina de Post-Turing, a argumentação de Davis em Steen (Steen 1980:251ff) deve ser útil.

Veja também

• Máquina de Turing que sempre para
• Arquitetura de von Neumann
• Turing Completude

Bibliografia

• Arora, Sanjeev; Barak, Boaz, "Complexity Theory: A Modern Approach", Cambridge University Press, 2009, ISBN 978-0-521-42426-4, section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"

Artigos de seminário

• F. C. Hennie and R. E. Stearns. Two-tape simulation of multitape Turing machines. JACM, 13(4):533–546, 1966.

Outras referências

• Copeland, Jack, ed. (2004). «The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma». Oxford UK: Oxford University Press. ISBN 0-19-825079-7 
• Davis, Martin (1980). Steen, Lynn Arthur, ed. «Mathematics Today: Twelve Informal Essays». What is Computation?. New York NY: Vintage Books (Random House). ISBN 978-0-394-74503-9 .
• Davis, Martin (2000). «Engines of Logic: Mathematicians and the origin of the Computer» 1st ed. New York NY: W. W. Norton & Company. ISBN 0-393-32229-7. (pb.) 
• Goldstine, Herman H., and von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study, Princeton. Reimpresso em pp. 92–119 in Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw-Hill Book Company, New York. ISBN 0-07-004357-4}.
• Herken, Rolf (1995). «The Universal Turing Machine – A Half-Century Survey». Springer Verlag. ISBN 3-211-82637-8 
• Knuth, Donald E. «The Art of Computer Programming Second Edition, Volume 1/Fundamental Algorithms» 2nd, 1973 ed. Addison-Wesley Publishing Company  A primeira da série de Knuth de 3 textos.
• Kudlek, Manfred; Rogozhin, Yurii (2002). «A universal Turing machine with 3 states and 9 symbols». Springer. LNCS. 2295: 311–318 
• Minsky, Marvin (1962). «Size and Structure of Universal Turing Machines using Tag Systems, Recursive Function Theory». Providence RI: American Mathematical Society. Proc. Symp. Pure Mathematics. 5: 229–238 
• Neary, Turlough; Woods, Damien (2009). «Four Small Universal Turing Machines» 1 ed. Fundamenta Informaticae. 91 
• Neary, Turlough; Woods, Damien (2009b). «Small Weakly Universal Turing Machines». Springer LNCS 5699. 17th International Symposium on Fundamentals of Computation Theory: 262–273 
• Penrose, Roger (1989). «The Emperor's New Mind». Oxford UK: Oxford University Press. ISBN 0-19-851973-7. (hc.), (pb.) 
• Rogozhin, Yurii (1996). «Small Universal Turing Machines» 2 ed. Theoretical Computer Science. 168: 215–240. doi:10.1016/S0304-3975(96)00077-1 
• Shannon, Claude (1956). «Automata Studies». A Universal Turing Machine with Two Internal States. Princeton, NJ: Princeton University Press: 157–165 
• Turing, Alan (1936). «On Computable Numbers, With an Application to the Entscheidungsproblem» 2 ed. Proceedings of the London Mathematical Society. 42  (and Turing, A.M. (1938). «On Computable Numbers, with an Application to the Entscheidungsproblem: A correction» 6 ed. (publicado em 1937). Proceedings of the London Mathematical Society. 2. 43: 544–6. doi:10.1112/plms/s2-43.6.544 ). Reprinted in Martin Davis ed. (1965) The Undecidable, Raven Press, Hewlett NY pp. 115–154; with corrections to Turing's UTM by Emil Post cf footnote 11 in Davis 1965:299.